"""
2654. 使数组所有元素变成 1 的最少操作次数
中等
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。
请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。



示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。


提示：

2 <= nums.length <= 50
1 <= nums[i] <= 106
"""
from math import gcd
from typing import List


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        """
        思路：尽快找到公约为1，找到后全部使用1来公约，即可得到最终次数 也就是res= 公约为1的次数 + (len - 1)
        :param nums:
        :return:
        """
        len1 = len(nums)
        ans = float("inf")
        if nums.count(1) > 0:
            return len1 - nums.count(1)
        for i,j in enumerate(nums):
            if j==1:
                ans = 0
            for k in range(i-1,-1,-1):
                gcd1 = gcd(nums[k], j)
                if gcd1 == nums[k]:
                    break
                nums[k] = gcd1
                if nums[k] == 1:
                    ans = min(ans,i - k)
        return ans + len1 - 1 if ans != float("inf") else -1
    def minOperations_gcd(self, nums: List[int]) -> int:
        if gcd(*nums) > 1:
            return -1
        n = len(nums)
        cnt1 = sum(x == 1 for x in nums)
        if cnt1:
            return n - cnt1

        min_size = n
        a = []  # [GCD，相同 GCD 闭区间的右端点]
        for i, x in enumerate(nums):
            a.append([x, i])

            # 原地去重，因为相同的 GCD 都相邻在一起
            j = 0
            for p in a:
                p[0] = gcd(p[0], x)
                if a[j][0] != p[0]:
                    j += 1
                    a[j] = p
                else:
                    a[j][1] = p[1]
            del a[j + 1:]

            if a[0][0] == 1:
                # 这里本来是 i-a[0][1]+1，把 +1 提出来合并到 return 中
                min_size = min(min_size, i - a[0][1])
        return min_size + n - 1

if __name__ == '__main__':
    print(Solution().minOperations([2,6,3,4])) #4
    print(Solution().minOperations([2,10,6,14])) #4
    print(Solution().minOperations([1,1])) #4

